package com.tgy.algorithm._经典题目01;


import java.util.*;

/**
 *
 * 【问题】字符串转换路径问题
 *         给定两个字符串，记为start和to，再给定一个字符串列表list，list中一定包含
 *         to，list中没有重复的字符串。所有字符串都是小写的。规定start每次只可以改
 *         变一个字符，最终的目标是彻底变成to，但每次变成的字符串都必须在list中存在。
 *         请返回最短的变换路径。
 * 【举例】
 *         start = "abc"
 *         to = "cab"
 *         list = {"cab","acc","cbc","ccc","cac","cbb","aab","abb"}
 *         转换路径的方法有很多种，但是最短的转换路径如下：
 *         abc --> abb --> aab --> cab
 *         abc --> abb --> cbb --> cab
 *         abc --> cbc --> cac --> cab
 *         abc --> cbc --> cbb --> cab
 * 【分析】
 *         本题目难度较大，需要拆分成四个步骤进行实现，接下来完成第一步骤获取每一个
 *         字符串的nexts信息。
 *
 * 【第一步】
 *         将start加入list，然后根据list生成每一个字符串的nexts信息。nexts具体是
 *         指如果朱改变一个字符，该字符串可以变成哪些字符串。比如上面的list，先把
 *         "abc"加入到list中，然后根据list生成信息如下：
 *         字符串    nexts信息(next要求属于list 否则丢弃)
 *         acc       abc ccc
 *         abb       aab cbb abc
 *         ccc       acc cac cbc
 *         cbb       abb cab cbc
 *         abc       abb cbc acc
 *         aab       abb cab
 *         cac       cbc cab ccc
 *         cab       aab cbb cac
 *         cbc       abc cac cbb ccc
 *
 *         如何判断生成的一个字符串是否在list内呢?
 *         首先把list中所有的字符串放入哈希表set中，这样检查某一个字符串是否在list中
 *         就可以通过查询set来实现，这样做的原因是哈希表查询的时间复杂度是O(1)，比遍
 *         历list查询某个字符串是否在其中速度要快很多。
 *
 *         如何生成字符串的nexts信息呢？
 *         因为每一个字符都是小写，所以看"bcc" "ccc" "dcc" "ecc" ..."zcc"哪些在set中，
 *         就把哪些放到"acc"的nexts列表中；然后看"aac" "abc" "adc" "aec" ... "azc"哪些
 *         在set中，就把哪些放到"acc"的nexts列表中；最后看"aca" "acb" "acd" ... "acz"
 *         哪些在set中，就把哪些放到"acc"的nexts列表中。也就是说，某个位置的字符都是从
 *         a --> z 开始枚举，哪些在set中就放到该元素的nexts列表中。
 *
 * @author 雪瞳
 * @Slogan 时钟尚且前行，人怎能再次止步！
 * @Function 返回没一个字符串的next信息
 *
 */
public class _031_字符串集合的最小路径 {

    public static List<List<String>> getAllShortestPath(String start,String to,String[] list) {

        if (start == null || to == null || list == null || list.length == 0) {
            return null;
        }

        List<String> strs = new ArrayList<>();
        for (String string : list) {
            strs.add(string);
        }
        strs.add(start);

        // 获取所有字符串的next的字符串
        HashMap<String, List<String>> nexts = getNexts(strs);
        // 找到starts到各个字符串的距离
        HashMap<String, Integer> distances = getStr2StrDistance(start, nexts);

        List<List<String>> rets = new ArrayList<>();
        List<String> path = new ArrayList<>();
        findMinPaths(start,to,nexts,distances,path,rets);
        return rets;
    }

    public static void findMinPaths(String from,
                                    String to,
                                    HashMap<String, List<String>> nexts,
                                    HashMap<String, Integer> distances,
                                    List<String> path,
                                    List<List<String>> results) {

        if (from.equals(to)) {
            ArrayList<String> list = new ArrayList<>(path);
            list.add(to);
            results.add(list);
            return;
        }
        path.add(from);
        List<String> nextStrs = nexts.get(from);
        for (String nextStr : nextStrs) {
            if (distances.get(from) + 1 == distances.get(nextStr)) {
                findMinPaths(nextStr,to,nexts,distances,path,results);
            }
        }
        path.remove(path.size() - 1);
    }

    public static HashMap<String,Integer> getStr2StrDistance(String start,HashMap<String,List<String>> nexts) {

        HashMap<String,Integer> distances = new HashMap<>();
        distances.put(start,0);
        // LinkedList是队列
        // PriorityQueue 是堆
        LinkedList<String> queue = new LinkedList<>();
        HashSet<String> visits = new HashSet<>();
        queue.add(start);
        visits.add(start);
        int level = 1;
        String leveLast = start;
        String nextLast = "";
        while (!queue.isEmpty()) {
            String cur = queue.poll();
            List<String> nextStrs = nexts.get(cur);
            for (String nextStr : nextStrs) {
                if (!visits.contains(nextStr)) {
                    queue.add(nextStr);
                    distances.put(nextStr,level);
                    System.out.println("cur: " + cur + " " + nextStr + " : level " + level + " ");
                    visits.add(nextStr);
                    nextLast = nextStr;
                }
            }
            if (cur == leveLast) {
                System.out.println("==============");
                level++;
                leveLast = nextLast;
                nextLast = "";
            }
        }

        return distances;
    }

    public static HashMap<String,List<String>> getNexts(List<String> strs) {

        HashMap<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            map.put(str,getNext(str,strs));
        }
        return map;
    }

    public static List<String> getNext(String curStr,List<String> strs) {

        HashSet<String> hashSet = new HashSet<>(strs);
        ArrayList<String> rets = new ArrayList<>();
        int len = curStr.length();
        char[] chars = curStr.toCharArray();
        for (int i = 0; i < len; i++) {
            char tmp = chars[i];
            for (int j = 0; j < 26 ; j++) {
                char c = (char)('a' + j);
                if (c == tmp) {
                    continue;
                }
                chars[i] = c;
                String val = new String(chars);
                if (hashSet.contains(val)) {
                    rets.add(val);
                }
            }
            chars[i] = tmp;
        }

        return rets;
    }

    public static void main(String[] args) {
        /**
         *              abc
         *         /  \     \
         *      cbc  acc     abb
         *          /       /   \
         *         ccc    cbb    aab
         *                      /
         *                    cab
         *                    /
         *                   cac
         */
        String[] list = {"cab","acc","cbc","ccc","cac","cbb","aab","abb"};
        List<List<String>> allShortestPath = getAllShortestPath("abc", "cab", list);
        allShortestPath.forEach(val->{
            System.out.println(val);
        });
    }
}
